My present invention relates to an analysis method and apparatus and, more particularly, to a system utilizing Fourier transformation methods for analyzing data and deriving useful information from spectrally analyzed signals, i.e. signals obtained from physical processes and in which there is a frequency variation and amplitudes associated with frequency of such signals.
In a number of imaging processes, it is common to subject an object to electromagnetic radiation over a broad spectral range and to analyze reflected or transmitted or scattered or back scattered radiation as a function of time to determine, for example, amplitude as a function of frequency or other parameters of the radiation.
By such methods, which frequently can utilize Fourier analysis of the signals of mixed or varying frequency, it is possible to measure a change in signal intensity as a function of time or a relationship between intensity and frequency which represents data providing information as to the analyzed object. The object can be a part of the human body, some other animate object, an inanimate object or a less tangible object such as speech, music or the like.
The analysis can involve decomposing a mixed frequency signal into different oscillation segments, for example, elemental frequencies, and determining the relative intensities of these segments at a point in time and/or variation of the amplitudes of the different frequencies as a function of time. Typically the analysis utilizes Fourier transformation (FT) and yields an indication of the components or shape or variation in density or presence or absence of cell masses or other patterns of the object.
Fourier transforms are thus used in a variety of image generating and spectroscopic analyses and methods.
In nuclear magnetic resonance spectroscopy, for example, the object can be irradiated with radiant energy pulses in the ultrashort wavelength range whereby protons or other atomic particles or nuclei absorb the applied energy and, depending upon their Larmor frequencies reemit energy. By measuring the time course of a summation signal from the radiation scanning or analysis of the object and utilizing Fourier transformation, for example, in nuclear magnetic resonance spectrometry, frequency spectra can be produced from the time spectra. It is thus possible to determine how many nuclei, for example, absorb or emit and at which frequencies and over the course of time.
An image can thus be generated of tissue densities in the human body and, if the calculation and analysis is done on a real time such images can be displayed and can be interpreted by skilled technicians to signal pathologies or the like.
There are other measurement processes utilizing the same or similar principles in, for example, computer tomography in which the applied radiation is x-ray radiation, magnetic resonance technology also utilizing ultrashort waves, music and spectral analyses of voice or other acoustic signals, as well as various process which utilize data compression (JPEG or MPEG).
The digitized results obtained are processed by, for example, DISCRETE FOURIER TRANSFORMATION (DFT) which yields results which can be treated in terms of the following formula.                                           A            n                    ⁢                      :                          =                              ∑                          k              =              0                                      N              -              1                                ⁢                      xe2x80x83                    ⁢                                    W              N              nk                        ⁢                          xe2x80x83                        ⁢                          a              k                                                          FORMULA        ⁢                  xe2x80x83                ⁢        1            
In Formula 1:
A=spectrum,
An=point in spectrum,
WN=Fourier Factor
N=Number of the Measuring point
a=Measuring Signal
ak=point in the measurement signal
n=run number=0, 1, 2, . . . Nxe2x88x921
k=summation index=0,1,2, . . . Nxe2x88x921
The Fourier factor WN in turn is equal to the value given in Formula 2
WN=exp (xc2x1i 2xcfx80/N)xe2x80x83xe2x80x83Formula 2
or in Formula 3
WNnk=exp (xc2x1i2xcfx80nk/N)xe2x80x83xe2x80x83Formula 3
In order to process the information especially quickly, the computer or analysis circuitry can be designed so that the right side of Formula 1 is decomposed into sums with even and odd indices k. AN can thus be given as shown in Formula 4,                               A          n                =                                                                              ∑                                      k                    =                    0                                                        N                    -                    1                                                  ⁢                                  xe2x80x83                                ⁢                                                      W                                          N                      /                      2                                                                                      n                        xe2x80x2                                            ⁢                                              xe2x80x83                                            ⁢                      k                                                        ⁢                                      xe2x80x83                                    ⁢                                      a                                          2                      ⁢                      k                                                                                  ⏟                                      =                                                :                                ⁢                                  xe2x80x83                                ⁢                                  A                                      n                    xe2x80x2                                                        (                    0                    )                                                                                +                                                                      W                  N                                      n                    xe2x80x2                                                  ⁢                                  xe2x80x83                                ⁢                                                      ∑                                          k                      =                      0                                                                                      N                        /                        2                                            -                      1                                                        ⁢                                      xe2x80x83                                    ⁢                                                            W                                              N                        /                        2                                                                                              n                          xe2x80x2                                                ⁢                                                  xe2x80x83                                                ⁢                        k                                                              ⁢                                          xe2x80x83                                        ⁢                                          a                                                                        2                          ⁢                          k                                                +                        1                                                                                                        ⏟                                      =                                                :                                ⁢                                  xe2x80x83                                ⁢                                  A                                      n                    xe2x80x2                                                        (                    1                    )                                                                                                          FORMULA        ⁢                  xe2x80x83                ⁢        4            
as the sum of two N/2-point Fourier transformations Anxe2x80x2(0) and Anxe2x80x2(1).
In this relationship:
nxe2x80x2=the number in the sequence of data points=0,1,2. . . ,N/2xe2x88x921
(0)=the even indices n
(1)=the odd indices n.
With this set of rules, measured information can be evaluated especially rapidly.
A discrete Fourier transformation with N complex value data points (N-Point-DFT) can be reduced by the following mixing rules to two N/2-point DFT:
Anxc2x7=An(0)+Wnxe2x80x2nAnxe2x80x2(1)xe2x80x83xe2x80x83Formula 5
Anxc2x7+N/2=Anxc2x7(0)xe2x88x92WNnxe2x80x2Anxc2x7(1)xe2x80x83xe2x80x83Formula 6
With
nxc2x7=0,1 . . . ,N/2xe2x88x921xe2x80x83xe2x80x83For Formulas 4, 5 and 6
If N is the second power, the calculation can be carried out in a fully recursive manner: An results by the mixing of Anxc2x7(0) and Anxc2x7(0), Anxc2x7(0) can be obtained by a mixing of An(00): =(An*(0)) (0) and An*(01):=(An*(0),), Anxe2x80x2(1)by a mixing of An*(10):=(An*(1)) (0)) and An*(11):=(Anxe2x80x3(1))(1) etc.
As the starting point for the recursion, the DFT according to Formulas 1 and 2 has individual values equal to this value itself. This means that for each sample of m: =Log2 (N) ones and zeroes, there is a 1-point DFT which corresponds to the input value
k xcex5 less than xe2x88x920,1, . . . , Nxe2x88x921 greater than : Ao(b1b2. . . bm)=akxe2x80x83xe2x80x83Formula 7
bixcex5 less than 0,1 greater than ; i=1,2, . . . mxe2x80x83xe2x80x83Formula 8
For the successive separation of the sum into even and odd indices, for the determination of k the bit sample (b1, b2, . . . bm) is only read from right to left:
A0(k)=abit-reversed(k)xe2x80x83xe2x80x83Formula 9
With:
k=0,1, . . . , Nxe2x88x921
which has been found to be cost effective in practice because of the shorter processing time.
It is, therefore, the principal object of the invention to provide a measurement process or method and a measurement apparatus or chip which significantly reduces the relative error and permits the Fourier transformation to be carried out more rapidly in earlier systems.
It is also an object of the invention to provide improved electronic circuitry for facilitating the improved measurement process or for incorporation in the improved measurement apparatus.
Still another object of the invention is to provide a system for a Fourier transformation of data, especially in image formation, whereby drawbacks of earlier systems are avoided.
These objects are achieved, in accordance with the invention in an automatic method which comprises the steps of:
(a) acquiring data-carrying signals representing a condition to be analyzed;
(b) subjecting the data-carrying signals to at least one conversion from one domain to at least one other domain by a Fourier transformation involving determination of a Fourier factor WN; and
(c) calculating the Fourier factor WN using a Factor II defined by the relationship:
xe2x80x83xcex94c1=cos xxe2x88x921=xe2x88x922 sin2 (x/2)
where x=2xcfx80/N and N=number of data points.
Preferably the Factor II is transformed in the relationships V and VII as follows:
xcex94cn+1=2 xcex94c1xc2x7cn+xcex94cnxe2x80x83xe2x80x83Relationship V,
xcex94sn+1=2 xcex94c1xc2x7sn+xcex94snxe2x80x83xe2x80x83Relationship VII.
The electronic circuitry in which the method of the invention is embedded can be a chip as will be discussed in greater detail below.
The term measurement process and the term measurement method is used here in the sense of a method which can extract frequency information from time signals or local information with local frequency signals or which derive time signals or local information from frequency information.
In particular, these terms are intended to refer to a frequency analysis process. The analyzed frequencies can be time frequencies or local frequencies related to object scanning or events generated by an object. Included in these categories are image producing processes like computer tomography from which measurement points are acquired and combined to from an image. In addition to CAT scans, nuclear magnetic resonance (NMR) involving nuclear magnetic resonance spectroscopy or image forming methods are covered. The measurement processes to which the invention are applicable include acoustic measurement processes and has been noted these can involve noise or sound analysis and the processes can be diagnostic processes on human patients or animals. Of course image forming techniques which involve inanimate objects are also intended to be covered.
When a measurement apparatus within the invention is considered, it is intended to include all apparatus which can acquire a time dependent signal capable of being interpreted by Fourier transformation. Examples include: nuclear magnetic resonance spectrometers and tomographs. Microphones for analyzing voice, noise and music signals, computer tomographs, speech regulation systems and systems for detecting, imaging or analyzing inanimate objects including recognition systems and safety or protective systems, for example, for detecting dangerous contents of a suitcase or the like at an airport.
A DFT based upon formulas 5, 6 and 9 is usually referred to as a fast Fourier transformation (FFT) since the number of calculating steps is reduced from that required for direct collection according to Formula 1 from N2 to Nlog2(N).
Reference is made to the identity exp(ix)=cos(x)+sin(x) which requires sine and cosine values for the above described procedure (calculation of the Fourier Factor WN) for arguments of the form nx where n=0,1, , . . . Nxe2x88x921 and x: 2xcfx80/N.
The addition theorem for trigonometric functions:
cos [(n+1)x]=cos (nx) cos xxe2x88x92sin (nx) sin xxe2x80x83xe2x80x83Formula 10
xe2x80x83sin [(n+1)x]=sin (nx) cos x+cos (nx) sin xxe2x80x83xe2x80x83Formula 11
with the formulas 10 and 11, one can operate with the fastest implementation of FFT as well be apparent from W. H. Press; Numerical Recipes in C; Cambridge University Press; ISBN 0 521 43108 5.
The measurement method, imaging process and chip programmed in accordance with the invention have, however, a not in considerable error ratio. Because of rounding errors at certain decimal positions, relative errors of several percent can arise which is undesirable. Because of the shorter operation time of the present invention, these do not pose major problems.